Algorithm Visualizer

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183

import RPi.GPIO as GPIO
import time

# Class define the LED panel


class Panel(object):
    # time variable
    delay = 0.000001
    frame_duration = 0.1
    # Define size of Screen
    width = 16
    length = 32
    # Define Pins
    # RGB Pin
    red1_pin = 27
    green1_pin = 15
    blue1_pin = 22
    red2_pin = 23
    green2_pin = 24
    blue2_pin = 25
    # Address Pin
    a_pin = 7
    b_pin = 8
    c_pin = 9
    # Other Pin
    clock_pin = 3
    latch_pin = 4
    oe_pin = 2

    def __init__(self):
        # init screen matrix
        self.screen = [[0 for x in range(self.length)]
                       for x in range(self.width)]
        # GPIO setups
        GPIO.setwarnings(False)
        GPIO.setmode(GPIO.BCM)
        GPIO.setup(self.red1_pin, GPIO.OUT)
        GPIO.setup(self.green1_pin, GPIO.OUT)
        GPIO.setup(self.blue1_pin, GPIO.OUT)
        GPIO.setup(self.red2_pin, GPIO.OUT)
        GPIO.setup(self.green2_pin, GPIO.OUT)
        GPIO.setup(self.blue2_pin, GPIO.OUT)
        GPIO.setup(self.clock_pin, GPIO.OUT)
        GPIO.setup(self.a_pin, GPIO.OUT)
        GPIO.setup(self.b_pin, GPIO.OUT)
        GPIO.setup(self.c_pin, GPIO.OUT)
        GPIO.setup(self.latch_pin, GPIO.OUT)
        GPIO.setup(self.oe_pin, GPIO.OUT)

    def clean_gpio(self):
        GPIO.cleanup()

    def clock(self):
        GPIO.output(self.clock_pin, 1)
        GPIO.output(self.clock_pin, 0)

    def latch(self):
        GPIO.output(self.latch_pin, 1)
        GPIO.output(self.latch_pin, 0)

    def bits_from_int(self, x):
        a_bit = x & 1
        b_bit = x & 2
        c_bit = x & 4
        return (a_bit, b_bit, c_bit)

    def set_row(self, row):
        a_bit, b_bit, c_bit = self.bits_from_int(row)
        GPIO.output(self.a_pin, a_bit)
        GPIO.output(self.b_pin, b_bit)
        GPIO.output(self.c_pin, c_bit)

    def set_color_top(self, color):
        red, green, blue = self.bits_from_int(color)
        GPIO.output(self.red1_pin, red)
        GPIO.output(self.green1_pin, green)
        GPIO.output(self.blue1_pin, blue)

    def set_color_bottom(self, color):
        red, green, blue = self.bits_from_int(color)
        GPIO.output(self.red2_pin, red)
        GPIO.output(self.green2_pin, green)
        GPIO.output(self.blue2_pin, blue)

    # refresh whole LED panel
    def refresh(self):
        for row in range(8):
            GPIO.setmode(GPIO.BCM)
            GPIO.output(self.oe_pin, 1)
            self.set_color_top(0)
            self.set_row(row)
            for col in range(32):
                self.set_color_top(self.screen[row][col])
                self.set_color_bottom(self.screen[row+8][col])
                self.clock()
            self.latch()
            GPIO.output(self.oe_pin, 0)
            time.sleep(self.delay)

    # keep refresh() for frame_duration
    # call this method every time a new screen should be displayed on the panel
    def frame(self):
        start_time = time.time()
        run = True
        while run:
            self.refresh()
            now_time = time.time()
            if (now_time - start_time > self.frame_duration):
                run = False

    def fill_rectangle(self, x1, y1, x2, y2, color):
        for x in range(x1, x2 + 1):
            for y in range(y1, y2 + 1):
                self.screen[y][x] = color

    # set one LED at (x, y) to color
    def set(self, x, y, color):
        # 0 <= x <= 31
        # 0 <= y <= 15
        # colors:
        # Black = 0
        # Red = 1
        # Green = 2
        # Yellow = 3
        # Blue = 4
        # Magenta = 5
        # Cyan = 6
        # White = 7
        if (x >= 0 and x < self.length and y >= 0 and y < self.width):
            self.screen[y][x] = color

    # draw a Point on the screen
    def draw_point(self, x, y, color):
        self.set(x, y, color)

    # draw a Node of tree or graph at (x, y) with color
    def draw_node(self, x, y, color):
        # delta of a cross shape
        delta = [(0, 0), (1, 0), (0, 1), (-1, 0), (0, -1)]
        for i, j in delta:
            self.set(x + i, y + j, color)

    # generate a Line from (x1, y1) to (x2, y2) with color
    # Only can generate a horizontal or vertical or diagonal line
    def draw_line(self, x1, y1, x2, y2, color):
        if not (x1 == x2 or y1 == y2 or abs(x2 - x1) == abs(y2 - y1)):
            raise ValueError(
                "Bad x1 = {}, y1 = {}, x2 = {}, y2 = {}! \n Only can generate a horizontal or vertical or diagonal line".format(x1, x2, y1, y2))

        delta = [(1, 0), (1, 1), (0, 1), (-1, 1),
                 (-1, 0), (-1, -1), (0, -1), (1, -1), (0, 0)]
        i = 0
        if (x2 > x1):
            if (y2 == y1):
                i = 0
            elif (y2 > y1):
                i = 1
            else:
                i = 7
        elif (x2 == x1):
            if (y2 == y1):
                i = 8
            elif (y2 > y1):
                i = 2
            else:
                i = 6
        else:
            if (y2 == y1):
                i = 4
            elif (y2 > y1):
                i = 3
            else:
                i = 5

        dx, dy = delta[i]

        if (x2 != x1):
            for i in range(0, abs(x2 - x1) + 1):
                self.set(x1 + i * dx, y1 + i * dy, color)
        else:
            for i in range(0, abs(y2 - y1) + 1):
                self.set(x1 + i * dx, y1 + i * dy, color)

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130

from panel import Panel
from line import Line


class Node(object):
    # bind Node with a screen object
    def __init__(self, x, y, color, screen, nid):
        if (not isinstance(screen, Panel)):
            raise ValueError("screen must be an object of class Panel!")
        else:
            self.id = nid
            self.x = x
            self.y = y
            self.color = color
            self.screen = screen

    # draw a point Node on screen, BUT no refresh, need refresh to display later
    def draw(self):
        # print("when draw node, node {}, color is {}".format(self.id, self.color))
        self.screen.draw_point(self.x, self.y, self.color)

    def change_color(self, color):
        self.color = color

    # return ((x1, y1), (x2, y2)) when connect this node to another node
    def connection_position(self, node):
        x1 = self.x
        y1 = self.y
        x2 = node.x
        y2 = node.y

        if (x1 == x2):
            if y2 < y1:
                return ((x1, y1 - 1), (x2, y2 + 1))
            else:
                return ((x1, y1 + 1), (x2, y2 - 1))
        elif (y1 == y2):
            if x2 < x1:
                return ((x1 - 1, y1), (x2 + 1, y2))
            else:
                return ((x1 + 1, y1), (x2 - 1, y2))
        elif (abs(x2 - x1) == abs(y2 - y1)):
            if x2 > x1:
                if y2 > y1:
                    return ((x1 + 1, y1 + 1), (x2 - 1, y2 - 1))
                elif y2 < y1:
                    return ((x1 + 1, y1 - 1), (x2 - 1, y2 + 1))
            elif x2 < x1:
                if y2 > y1:
                    return ((x1 - 1, y1 + 1), (x2 + 1, y2 - 1))
                elif y2 < y1:
                    return ((x1 - 1, y1 - 1), (x2 + 1, y2 + 1))

    # return an instance of class Line that connects two cross nodes
    def line_connect_to(self, node, color):
        ((x1, y1), (x2, y2)) = self.connection_position(node)
        return Line(x1, y1, x2, y2, color, self.screen)

    def get_id(self):
        return self.id


# TreeNode inherited from class Node
# TreeNode has parent, children
class TreeNode(Node):
    def __init__(self, x, y, color, screen, nid):
        super().__init__(x, y, color, screen, nid)
        self.parent = None
        self.line = None
        self.left = None
        self.right = None

    def set_children(self, left, right):
        self.left = left
        self.right = right

    def set_left(self, left):
        self.left = left

    def set_right(self, right):
        self.right = right

    def get_children(self):
        return (self.left, self.right)

    def get_left(self):
        return self.left

    def get_right(self):
        return self.right

    def set_parent(self, parent):
        self.parent = parent

    def get_parent(self):
        return self.parent

    # For each TreeNode, it has only one line from parent to it
    def set_line(self, line):
        self.line = line

    def get_line(self):
        return self.line

    def isLeaf(self):
        return self.left == None and self.right == None

    def isRoot(self):
        return self.parent == None


class GraphNode(Node):
    def __init__(self, x, y, node_color, edge_color, screen, nid):
        super().__init__(x, y, node_color, screen, nid)
        # self.neighbors = set()
        self.edges = {}
        self.visited = False

    def mark_visited(self):
        self.visited = True

    def new_edge_to(self, node, edge_color):
        return self.line_connect_to(node, edge_color)

    def add_neighbor(self, node, edge):
        # self.neighbors.add(node)
        self.edges[node] = edge

    def get_edges(self):
        return self.edges

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129

from panel import Panel
from line import Line


class Node(object):
    # bind Node with a screen object
    def __init__(self, x, y, color, screen, nid):
        if (not isinstance(screen, Panel)):
            raise ValueError("screen must be an object of class Panel!")
        else:
            self.id = nid
            self.x = x
            self.y = y
            self.color = color
            self.screen = screen

    # draw a cross Node on screen, BUT no refresh, need refresh to display later
    def draw(self):
        # print("when draw node, node {}, color is {}".format(self.id, self.color))
        self.screen.draw_node(self.x, self.y, self.color)

    def change_color(self, color):
        self.color = color

    # return ((x1, y1), (x2, y2)) when connect this node to another node
    def connection_position(self, node):
        x1 = self.x
        y1 = self.y
        x2 = node.x
        y2 = node.y

        if (x1 == x2):
            if y2 < y1:
                return ((x1, y1 - 2), (x2, y2 + 2))
            else:
                return ((x1, y1 + 2), (x2, y2 - 2))
        elif (y1 == y2):
            if x2 < x1:
                return ((x1 - 2, y1), (x2 + 2, y2))
            else:
                return ((x1 + 2, y1), (x2 - 2, y2))
        elif (abs(x2 - x1) == abs(y2 - y1)):
            if x2 > x1:
                if y2 > y1:
                    return ((x1 + 1, y1 + 1), (x2 - 1, y2 - 1))
                elif y2 < y1:
                    return ((x1 + 1, y1 - 1), (x2 - 1, y2 + 1))
            elif x2 < x1:
                if y2 > y1:
                    return ((x1 - 1, y1 + 1), (x2 + 1, y2 - 1))
                elif y2 < y1:
                    return ((x1 - 1, y1 - 1), (x2 + 1, y2 + 1))

    # return an instance of class Line that connects two cross nodes
    def line_connect_to(self, node, color):
        ((x1, y1), (x2, y2)) = self.connection_position(node)
        return Line(x1, y1, x2, y2, color, self.screen)

    def get_id(self):
        return self.id


# TreeNode inherited from class Node
# TreeNode has parent, children
class TreeNode(Node):
    def __init__(self, x, y, color, screen, nid):
        super().__init__(x, y, color, screen, nid)
        self.parent = None
        self.line = None
        self.left = None
        self.right = None

    def set_children(self, left, right):
        self.left = left
        self.right = right

    def set_left(self, left):
        self.left = left

    def set_right(self, right):
        self.right = right

    def get_children(self):
        return (self.left, self.right)

    def get_left(self):
        return self.left

    def get_right(self):
        return self.right

    def set_parent(self, parent):
        self.parent = parent

    def get_parent(self):
        return self.parent

    # For each TreeNode, it has only one line from parent to it
    def set_line(self, line):
        self.line = line

    def get_line(self):
        return self.line

    def isLeaf(self):
        return self.left == None and self.right == None

    def isRoot(self):
        return self.parent == None


class GraphNode(Node):
    def __init__(self, x, y, node_color, edge_color, screen, nid):
        super().__init__(x, y, node_color, screen, nid)
        # self.neighbors = set()
        self.edges = {}
        self.visited = False

    def mark_visited(self):
        self.visited = True

    def new_edge_to(self, node, edge_color):
        return self.line_connect_to(node, edge_color)

    def add_neighbor(self, node, edge):
        self.edges[node] = edge

    def get_edges(self):
        return self.edges

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

from panel import Panel


class Line(object):
    def __init__(self, x1, y1, x2, y2, color, screen):
        if (not isinstance(screen, Panel)):
            raise ValueError("screen must be an instance of class Panel!")
        else:
            self.color = color
            self.screen = screen
            self.x1 = x1
            self.y1 = y1
            self.x2 = x2
            self.y2 = y2

    # draw this Line on screen, BUT no refresh, need refresh to display later
    def draw(self):
        self.screen.draw_line(self.x1, self.y1, self.x2, self.y2, self.color)

    def change_color(self, color):
        self.color = color

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253

import random
from panel import Panel
from node_point import TreeNode
from collections import deque


class Tree(object):
    def __init__(self, screen):
        if (not isinstance(screen, Panel)):
            raise ValueError("screen must be an object of class Panel!")
        else:
            self.screen = screen
            self.nodes = []
            self.lines = []
            self.node_num = 0
            self.line_num = 0
            self.root = None
            self.duration = 1
            # set node_color to WHITE as default
            self.node_color = 3
            # set line_color to GREEN as default
            self.line_color = 7
            # set visited node color to RED as default
            self.visited_node_color = 1
            # set visited line color to GREEN as default
            self.visited_line_color = 2

    # set node and line color of this tree
    # avoid setting color after having nodes or lines
    def set_color(self, node_color, line_color, visited_node_color, visited_line_color):
        self.node_color = node_color
        self.line_color = line_color
        self.visited_node_color = visited_node_color
        self.visited_line_color = visited_line_color

    # set duration
    def set_duration(self, duration):
        self.duration = duration

    # return a new node at (x, y)
    def new_node(self, x, y):
        return TreeNode(x, y, self.node_color, self.screen, self.node_num)

    # return the line that connects two existing node in this tree with line
    # node1 should be parent node
    # node2 should be children node
    def new_connection(self, node1, node2):
        line = node1.line_connect_to(node2, self.line_color)
        if (node2.x < node1.x):
            node1.set_left(node2)
        else:
            node1.set_right(node2)
        node2.set_parent(node1)
        node2.set_line(line)
        return line

    # add new node instance to nodes
    def add_node(self, x, y):
        self.nodes.append(self.new_node(x, y))
        self.node_num += 1

    # add new line instance to lines
    def add_line(self, node1, node2):
        self.lines.append(self.new_connection(node1, node2))
        self.line_num += 1

    # draw this tree on screen
    def draw_tree(self):
        for node in self.nodes:
            node.draw()
        for line in self.lines:
            line.draw()

    # return a random group of positions of nodes in a large tree
    def large_tree_nodes(self):
        nodes_group = [(15, 1), (12, 4), (18, 4), (9, 7), (15, 7), (21, 7), (6, 10), (
            12, 10), (18, 10), (24, 10), (3, 13), (9, 13), (15, 13), (21, 13), (27, 13)]

        delta = [(0, 0), (1, 0), (2, 0), (3, 0), (-1, 0), (-2, 0),
                 (0, 1), (1, 1), (2, 1), (3, 1), (-1, 1), (-2, 1)]

        i = random.randint(0, len(delta) - 1)
        print("use nodes group {}".format(i))
        dx, dy = delta[i]
        for i in range(0, len(nodes_group)):
            x, y = nodes_group[i]
            nodes_group[i] = (x + dx, y + dy)
        return nodes_group

    # connect a group of nodes in a large tree
    def connect_large_tree(self):
        lines = []
        lines1 = [(0, 1), (0, 2), (1, 3), (2, 4), (2, 5), (3, 6), (3, 7),
                  (4, 8), (5, 9), (6, 10), (7, 11), (8, 12), (8, 13), (9, 14)]
        lines2 = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (3, 6), (4, 7),
                  (4, 8), (5, 9), (6, 10), (7, 11), (8, 12), (8, 13), (9, 14)]
        lines3 = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (3, 6), (4, 7),
                  (4, 8), (5, 9), (6, 10), (7, 11), (7, 12), (9, 13), (9, 14)]
        lines4 = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (3, 6), (4, 7),
                  (5, 8), (5, 9), (6, 10), (6, 11), (7, 12), (9, 13), (9, 14)]
        lines5 = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (3, 6), (3, 7),
                  (5, 8), (5, 9), (6, 10), (6, 11), (8, 12), (9, 13), (9, 14)]
        lines6 = [(0, 1), (0, 2), (1, 3), (2, 4), (2, 5), (3, 6), (4, 7),
                  (5, 8), (5, 9), (6, 10), (6, 11), (7, 12), (8, 13), (9, 14)]
        lines.append(lines1)
        lines.append(lines2)
        lines.append(lines3)
        lines.append(lines4)
        lines.append(lines5)
        lines.append(lines6)
        i = random.randint(0, 5)
        print("use line {}".format(i))
        for n1, n2 in lines[i]:
            self.add_line(self.nodes[n1], self.nodes[n2])

    # generate a large tree
    def generate_large_tree(self):
        # generate 15 TreeNodes
        nodes_position = self.large_tree_nodes()
        for x, y in nodes_position:
            self.add_node(x, y)
        # set the first node as the root node of this tree
        self.root = self.nodes[0]
        # generate 14 lines
        self.connect_large_tree()

    # draw a large tree on screen
    def draw_large_tree(self):
        # print("call draw_large_tree()")
        self.generate_large_tree()
        self.draw_tree()

    # display tree on panel
    def display_tree(self, times):
        for i in range(times):
            self.screen.frame()

    # update color of a node in this tree
    def update_node_color(self, node_id, color):
        # print("before change, color is {}".format(self.nodes[node_id].color))
        self.nodes[node_id].change_color(color)
        # print("after change, color is {}".format(self.nodes[node_id].color))

    # update color of a line of a node in this tree
    def update_line_color(self, node_id, color):
        self.nodes[node_id].get_line().change_color(color)

    # visit the line of this node
    def visit_line(self, node):
        node_id = node.get_id()
        self.update_line_color(node_id, self.visited_line_color)
        self.draw_tree()
        self.display_tree(self.duration)

    # leave the line of this node
    def leave_line(self, node):
        node_id = node.get_id()
        self.update_line_color(node_id, self.line_color)
        self.draw_tree()
        self.display_tree(self.duration)

    # visit the node alone
    def visit_node(self, node):
        # print("visit node {}".format(node.get_id()))
        node_id = node.get_id()
        # print("visit node {}, want to change to color {}".format(
        #     node_id, self.visited_node_color))
        self.update_node_color(node_id, self.visited_node_color)
        self.draw_tree()
        self.display_tree(self.duration)

    # entry for inorder traversal
    def inorder_traversal(self):
        self.inorder_recursion(self.root)

    # recursive function for inorder traversal
    def inorder_recursion(self, node):
        # visit left child first
        left = node.get_left()
        if (left != None):
            self.visit_line(left)
            self.inorder_recursion(left)
        # visit this node then
        self.visit_node(node)
        right = node.get_right()
        # visit right child last
        if (right != None):
            self.visit_line(right)
            self.inorder_recursion(right)
        # after visiting this subtree, leave this line
        if (not node.isRoot()):
            self.leave_line(node)

    # entry for preorder traversal
    def preorder_traversal(self):
        self.preorder_recursion(self.root)

    # recursive function for preorder traversal
    def preorder_recursion(self, node):
        # visit this node first
        self.visit_node(node)
        # visit left child then
        left = node.get_left()
        if (left != None):
            self.visit_line(left)
            self.preorder_recursion(left)
        right = node.get_right()
        # visit right child last
        if (right != None):
            self.visit_line(right)
            self.preorder_recursion(right)
        # after visiting this subtree, leave this line
        if (not node.isRoot()):
            self.leave_line(node)

    # entry for postorder traversal
    def postorder_traversal(self):
        self.postorder_recursion(self.root)

    # recursive function for preorder traversal
    def postorder_recursion(self, node):
        # visit left child fist
        left = node.get_left()
        if left:
            self.visit_line(left)
            self.postorder_recursion(left)
        right = node.get_right()
        # visit right child then
        if right:
            self.visit_line(right)
            self.postorder_recursion(right)
        # visit this node last
        self.visit_node(node)
        # after visiting this subtree, leave this line
        if (not node.isRoot()):
            self.leave_line(node)

    def levelorder_traversal(self):
        queue = deque([self.root, ])

        while queue:
            n = len(queue)
            for i in range(n):
                node = queue.popleft()
                if (not node.isRoot()):
                    self.visit_line(node)
                self.visit_node(node)
                left = node.get_left()
                right = node.get_right()
                if left:
                    queue.append(left)
                if right:
                    queue.append(right)

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253

import random
from panel import Panel
from node_cross import TreeNode
from collections import deque


class Tree(object):
    def __init__(self, screen):
        if (not isinstance(screen, Panel)):
            raise ValueError("screen must be an object of class Panel!")
        else:
            self.screen = screen
            self.nodes = []
            self.lines = []
            self.node_num = 0
            self.line_num = 0
            self.root = None
            self.duration = 1
            # set node_color to WHITE as default
            self.node_color = 3
            # set line_color to GREEN as default
            self.line_color = 7
            # set visited node color to RED as default
            self.visited_node_color = 1
            # set visited line color to GREEN as default
            self.visited_line_color = 2

    # set node and line color of this tree
    # avoid setting color after having nodes or lines
    def set_color(self, node_color, line_color, visited_node_color, visited_line_color):
        self.node_color = node_color
        self.line_color = line_color
        self.visited_node_color = visited_node_color
        self.visited_line_color = visited_line_color

    # set duration
    def set_duration(self, duration):
        self.duration = duration

    # return a new node at (x, y)
    def new_node(self, x, y):
        return TreeNode(x, y, self.node_color, self.screen, self.node_num)

    # return the line that connects two existing node in this tree with line
    # node1 should be parent node
    # node2 should be children node
    def new_connection(self, node1, node2):
        line = node1.line_connect_to(node2, self.line_color)
        if (node2.x < node1.x):
            node1.set_left(node2)
        else:
            node1.set_right(node2)
        node2.set_parent(node1)
        node2.set_line(line)
        return line

    # add new node instance to nodes
    def add_node(self, x, y):
        self.nodes.append(self.new_node(x, y))
        self.node_num += 1

    # add new line instance to lines
    def add_line(self, node1, node2):
        self.lines.append(self.new_connection(node1, node2))
        self.line_num += 1

    # draw this tree on screen
    def draw_tree(self):
        for node in self.nodes:
            node.draw()
        for line in self.lines:
            line.draw()

    # return a random group of positions of nodes in a large tree
    def large_tree_nodes(self):
        nodes_group = [(15, 1), (12, 4), (18, 4), (9, 7), (15, 7), (21, 7), (6, 10), (
            12, 10), (18, 10), (24, 10), (3, 13), (9, 13), (15, 13), (21, 13), (27, 13)]

        delta = [(0, 0), (1, 0), (2, 0), (3, 0), (-1, 0), (-2, 0),
                 (0, 1), (1, 1), (2, 1), (3, 1), (-1, 1), (-2, 1)]

        i = random.randint(0, len(delta) - 1)
        print("use nodes group {}".format(i))
        dx, dy = delta[i]
        for i in range(0, len(nodes_group)):
            x, y = nodes_group[i]
            nodes_group[i] = (x + dx, y + dy)
        return nodes_group

    # connect a group of nodes in a large tree
    def connect_large_tree(self):
        lines = []
        lines1 = [(0, 1), (0, 2), (1, 3), (2, 4), (2, 5), (3, 6), (3, 7),
                  (4, 8), (5, 9), (6, 10), (7, 11), (8, 12), (8, 13), (9, 14)]
        lines2 = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (3, 6), (4, 7),
                  (4, 8), (5, 9), (6, 10), (7, 11), (8, 12), (8, 13), (9, 14)]
        lines3 = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (3, 6), (4, 7),
                  (4, 8), (5, 9), (6, 10), (7, 11), (7, 12), (9, 13), (9, 14)]
        lines4 = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (3, 6), (4, 7),
                  (5, 8), (5, 9), (6, 10), (6, 11), (7, 12), (9, 13), (9, 14)]
        lines5 = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (3, 6), (3, 7),
                  (5, 8), (5, 9), (6, 10), (6, 11), (8, 12), (9, 13), (9, 14)]
        lines6 = [(0, 1), (0, 2), (1, 3), (2, 4), (2, 5), (3, 6), (4, 7),
                  (5, 8), (5, 9), (6, 10), (6, 11), (7, 12), (8, 13), (9, 14)]
        lines.append(lines1)
        lines.append(lines2)
        lines.append(lines3)
        lines.append(lines4)
        lines.append(lines5)
        lines.append(lines6)
        i = random.randint(0, 5)
        print("use line {}".format(i))
        for n1, n2 in lines[i]:
            self.add_line(self.nodes[n1], self.nodes[n2])

    # generate a large tree
    def generate_large_tree(self):
        # generate 15 TreeNodes
        nodes_position = self.large_tree_nodes()
        for x, y in nodes_position:
            self.add_node(x, y)
        # set the first node as the root node of this tree
        self.root = self.nodes[0]
        # generate 14 lines
        self.connect_large_tree()

    # draw a large tree on screen
    def draw_large_tree(self):
        # print("call draw_large_tree()")
        self.generate_large_tree()
        self.draw_tree()

    # display tree on panel
    def display_tree(self, times):
        for i in range(times):
            self.screen.frame()

    # update color of a node in this tree
    def update_node_color(self, node_id, color):
        # print("before change, color is {}".format(self.nodes[node_id].color))
        self.nodes[node_id].change_color(color)
        # print("after change, color is {}".format(self.nodes[node_id].color))

    # update color of a line of a node in this tree
    def update_line_color(self, node_id, color):
        self.nodes[node_id].get_line().change_color(color)

    # visit the line of this node
    def visit_line(self, node):
        node_id = node.get_id()
        self.update_line_color(node_id, self.visited_line_color)
        self.draw_tree()
        self.display_tree(self.duration)

    # leave the line of this node
    def leave_line(self, node):
        node_id = node.get_id()
        self.update_line_color(node_id, self.line_color)
        self.draw_tree()
        self.display_tree(self.duration)

    # visit the node alone
    def visit_node(self, node):
        # print("visit node {}".format(node.get_id()))
        node_id = node.get_id()
        # print("visit node {}, want to change to color {}".format(
        #     node_id, self.visited_node_color))
        self.update_node_color(node_id, self.visited_node_color)
        self.draw_tree()
        self.display_tree(self.duration)

    # entry for inorder traversal
    def inorder_traversal(self):
        self.inorder_recursion(self.root)

    # recursive function for inorder traversal
    def inorder_recursion(self, node):
        # visit left child first
        left = node.get_left()
        if (left != None):
            self.visit_line(left)
            self.inorder_recursion(left)
        # visit this node then
        self.visit_node(node)
        right = node.get_right()
        # visit right child last
        if (right != None):
            self.visit_line(right)
            self.inorder_recursion(right)
        # after visiting this subtree, leave this line
        if (not node.isRoot()):
            self.leave_line(node)

    # entry for preorder traversal
    def preorder_traversal(self):
        self.preorder_recursion(self.root)

    # recursive function for preorder traversal
    def preorder_recursion(self, node):
        # visit this node first
        self.visit_node(node)
        # visit left child then
        left = node.get_left()
        if (left != None):
            self.visit_line(left)
            self.preorder_recursion(left)
        right = node.get_right()
        # visit right child last
        if (right != None):
            self.visit_line(right)
            self.preorder_recursion(right)
        # after visiting this subtree, leave this line
        if (not node.isRoot()):
            self.leave_line(node)

    # entry for postorder traversal
    def postorder_traversal(self):
        self.postorder_recursion(self.root)

    # recursive function for preorder traversal
    def postorder_recursion(self, node):
        # visit left child fist
        left = node.get_left()
        if left:
            self.visit_line(left)
            self.postorder_recursion(left)
        right = node.get_right()
        # visit right child then
        if right:
            self.visit_line(right)
            self.postorder_recursion(right)
        # visit this node last
        self.visit_node(node)
        # after visiting this subtree, leave this line
        if (not node.isRoot()):
            self.leave_line(node)

    def levelorder_traversal(self):
        queue = deque([self.root, ])

        while queue:
            n = len(queue)
            for i in range(n):
                node = queue.popleft()
                if (not node.isRoot()):
                    self.visit_line(node)
                self.visit_node(node)
                left = node.get_left()
                right = node.get_right()
                if left:
                    queue.append(left)
                if right:
                    queue.append(right)

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250

from panel import Panel
from node_point import GraphNode
from collections import deque
from random import randint


class Graph(object):
    def __init__(self, screen):
        if (not isinstance(screen, Panel)):
            raise ValueError("screen must be an object of class Panel!")
        else:
            self.screen = screen
            self.adjlist = []
            self.nodes = []
            self.edges = []
            self.node_num = 0
            self.edge_num = 0
            self.root = None
            self.duration = 1

            # set node_color to WHITE as default
            self.node_color = 3
            # set edge_color to GREEN as default
            self.edge_color = 7
            # set visited node color to RED as default
            self.visited_node_color = 1
            # set visited edge color to GREEN as default
            self.visited_edge_color = 2

    def set_duration(self, duration):
        self.duration = duration

    # set node and line color of this graph
    # avoid setting color after having nodes or lines
    def set_color(self, node_color, edge_color, visited_node_color, visited_edge_color):
        self.node_color = node_color
        self.edge_color = edge_color
        self.visited_node_color = visited_node_color
        self.visited_edge_color = visited_edge_color

    # return a new node at (x, y)
    def new_node(self, x, y):
        return GraphNode(x, y, self.node_color, self.edge_color, self.screen, self.node_num)

    def add_node(self, x, y):
        self.nodes.append(self.new_node(x, y))
        self.node_num += 1

    def new_edge(self, node1, node2):
        edge = node1.new_edge_to(node2, self.edge_color)
        node1.add_neighbor(node2, edge)
        node2.add_neighbor(node1, edge)
        return edge

    def add_edge(self, node1, node2):
        self.edges.append(self.new_edge(node1, node2))
        self.edge_num += 1

    # draw this graph on screen
    def draw_graph(self):
        for node in self.nodes:
            node.draw()
        for edge in self.edges:
            edge.draw()

    # return a random group  of postions of nodes in a large graph
    def large_graph_nodes(self):
        nodes_group1 = [
            (5, 2), (12, 2), (17, 1), (27, 1), (1, 6),
            (5, 5), (9, 5), (16, 6), (19, 3), (22, 6),
            (27, 6), (30, 3), (1, 13), (4, 10), (12, 8),
            (14, 10), (19, 10), (27, 11), (30, 8), (7, 13),
            (11, 13), (15, 14), (23, 14), (30, 14), (22, 11)
        ]

        return nodes_group1

    # return a random group  of edges in a large graph
    def large_graph_edges(self):
        edges1 = [
            (0, 1), (0, 4), (1, 7), (1, 14), (1, 6),
            (5, 6), (2, 3), (2, 8), (7, 8), (8, 9),
            (8, 16), (3, 9), (3, 10), (10, 11), (11, 18),
            (4, 12), (6, 13), (12, 13), (12, 19), (14, 19),
            (19, 20), (15, 20), (6, 14), (14, 15), (15, 16),
            (16, 21), (9, 24), (21, 22), (16, 22), (17, 24),
            (9, 17), (9, 10), (10, 17), (17, 18), (18, 23),
            (22, 23), (17, 23)
        ]

        edges2 = [
            (0, 1), (1, 7), (1, 14), (1, 6),
            (5, 6), (2, 3), (2, 8), (7, 8), (8, 9),
            (8, 16), (3, 9), (3, 10), (10, 11), (11, 18),
            (4, 12), (12, 13), (12, 19), (14, 19),
            (19, 20), (15, 20), (6, 14), (14, 15), (15, 16),
            (16, 21), (9, 24), (16, 22), (17, 24),
            (9, 10), (17, 18), (18, 23),
            (22, 23), (17, 23)
        ]

        edges3 = [
            (0, 1), (0, 4), (1, 7), (1, 14), (1, 6),
            (5, 6), (2, 8), (7, 8), (8, 9),
            (8, 16), (3, 9), (3, 10), (11, 18),
            (4, 12), (12, 13), (12, 19), (14, 19),
            (19, 20), (15, 20), (6, 14), (15, 16),
            (16, 21), (9, 24), (21, 22), (16, 22), (17, 24),
            (9, 17), (9, 10), (10, 17), (17, 18), (18, 23),
            (22, 23), (17, 23)
        ]

        edges4 = [
            (0, 1), (0, 4), (1, 7), (1, 14), (1, 6),
            (5, 6), (2, 3), (2, 8), (7, 8), (8, 9),
            (8, 16), (3, 9), (3, 10), (10, 11), (11, 18),
            (4, 12), (6, 13), (12, 13), (12, 19), (14, 19),
            (19, 20), (6, 14), (14, 15), (15, 16),
            (16, 21), (21, 22), (16, 22), (17, 24),
            (9, 17), (9, 10), (17, 18), (18, 23),
            (22, 23), (17, 23)
        ]

        edges5 = [
            (0, 1), (0, 4), (1, 7), (1, 14), (1, 6),
            (5, 6), (2, 3), (2, 8), (7, 8),
            (3, 10), (10, 11), (11, 18),
            (4, 12), (6, 13), (12, 13), (12, 19), (14, 19),
            (19, 20), (15, 20), (6, 14), (14, 15), (15, 16),
            (16, 21), (21, 22), (16, 22), (17, 24),
            (9, 17), (10, 17), (17, 18), (18, 23),
            (22, 23), (17, 23)
        ]

        edges6 = [
            (0, 1), (0, 4), (1, 7), (1, 6),
            (5, 6), (2, 3), (2, 8), (7, 8), (8, 9),
            (8, 16), (3, 9), (3, 10), (10, 11), (11, 18),
            (4, 12), (6, 13), (12, 13), (12, 19), (14, 19),
            (19, 20), (15, 20), (15, 16),
            (16, 21), (21, 22), (16, 22), (17, 24),
            (9, 10), (10, 17), (17, 18), (18, 23),
            (22, 23), (17, 23), (13, 19)
        ]
        edges = []
        edges.append(edges1)
        edges.append(edges2)
        edges.append(edges3)
        edges.append(edges4)
        edges.append(edges5)
        edges.append(edges6)
        i = randint(0, 5)
        return edges[i]

    # generate a large graph
    def generate_large_graph(self):
        # generate all nodes
        nodes_positions = self.large_graph_nodes()
        for x, y in nodes_positions:
            self.add_node(x, y)
        # generate all edges
        nodes_connections = self.large_graph_edges()
        for n1, n2 in nodes_connections:
            self.add_edge(self.nodes[n1], self.nodes[n2])

    # set the start node of graph algorithm
    def set_root(self, node_id):
        self.root = self.nodes[node_id]

    # draw a large graph on the screen
    def draw_large_graph(self):
        self.generate_large_graph()
        self.draw_graph()

    # display graph on panel
    def display_graph(self, times):
        for i in range(times):
            self.screen.frame()

    # update color of a node in this graph
    def update_node_color(self, node, color):
        node_id = node.get_id()
        self.nodes[node_id].change_color(color)

    # update color of a node in this graph
    def update_edge_color(self, edge, color):
        edge.change_color(color)

    # visit the edge
    def visit_edge(self, edge):
        self.update_edge_color(edge, self.visited_edge_color)
        self.draw_graph()
        self.display_graph(self.duration)

    # leave the edge
    def leave_edge(self, edge):
        self.update_edge_color(edge, self.edge_color)
        self.draw_graph()
        self.display_graph(self.duration)

    # visit the node alone
    def visit_node(self, node):
        node.mark_visited()
        self.update_node_color(node, self.visited_node_color)
        self.draw_graph()
        self.display_graph(self.duration)

    # entry for BFS
    def bfs_start(self):
        if (self.root == None):
            self.root = self.nodes[9]
        self.bfs(self.root)

    # BFS Algorithm
    def bfs(self, root):
        queue_node = deque([root, ])
        queue_edge = deque([])

        while queue_node:
            n = len(queue_node)
            for i in range(n):
                node = queue_node.popleft()
                if (not node.visited):
                    if (queue_edge):
                        edge_from = queue_edge.popleft()
                        self.visit_edge(edge_from)

                    self.visit_node(node)
                    for neighbor, edge in node.get_edges().items():
                        queue_node.append(neighbor)
                        queue_edge.append(edge)
                else:
                    if (queue_edge):
                        edge_from = queue_edge.popleft()

    # entry for DFS
    def dfs_start(self):
        if (self.root == None):
            self.root = self.nodes[9]
        self.dfs(self.root)

    # DFS Algorithm
    def dfs(self, node):
        self.visit_node(node)

        for neighbor, edge in node.get_edges().items():
            if not neighbor.visited:
                self.visit_edge(edge)
                self.dfs(neighbor)
                self.leave_edge(edge)

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251

from panel import Panel
from node_cross import GraphNode
from collections import deque
from random import randint


class Graph(object):
    def __init__(self, screen):
        if (not isinstance(screen, Panel)):
            raise ValueError("screen must be an object of class Panel!")
        else:
            self.screen = screen
            self.adjlist = []
            self.nodes = []
            self.edges = []
            self.node_num = 0
            self.edge_num = 0
            self.root = None
            self.duration = 1

            # set node_color to WHITE as default
            self.node_color = 3
            # set edge_color to GREEN as default
            self.edge_color = 7
            # set visited node color to RED as default
            self.visited_node_color = 1
            # set visited edge color to GREEN as default
            self.visited_edge_color = 2

    def set_duration(self, duration):
        self.duration = duration

    # set node and line color of this graph
    # avoid setting color after having nodes or lines
    def set_color(self, node_color, edge_color, visited_node_color, visited_edge_color):
        self.node_color = node_color
        self.edge_color = edge_color
        self.visited_node_color = visited_node_color
        self.visited_edge_color = visited_edge_color

    # return a new node at (x, y)
    def new_node(self, x, y):
        return GraphNode(x, y, self.node_color, self.edge_color, self.screen, self.node_num)

    def add_node(self, x, y):
        self.nodes.append(self.new_node(x, y))
        self.node_num += 1

    def new_edge(self, node1, node2):
        edge = node1.new_edge_to(node2, self.edge_color)
        node1.add_neighbor(node2, edge)
        node2.add_neighbor(node1, edge)
        return edge

    def add_edge(self, node1, node2):
        self.edges.append(self.new_edge(node1, node2))
        self.edge_num += 1

    # draw this graph on screen
    def draw_graph(self):
        for node in self.nodes:
            node.draw()
        for edge in self.edges:
            edge.draw()

    # return a random group  of postions of nodes in a large graph
    def large_graph_nodes(self):
        nodes_group1 = [
            (5, 2), (12, 2), (17, 1), (27, 1), (1, 6),
            (5, 5), (9, 5), (16, 6), (19, 3), (22, 6),
            (27, 6), (30, 3), (1, 13), (4, 10), (12, 8),
            (14, 10), (19, 10), (27, 11), (30, 8), (7, 13),
            (11, 13), (15, 14), (23, 14), (30, 14), (22, 11)
        ]

        return nodes_group1

    # return a random group  of edges in a large graph
    def large_graph_edges(self):
        edges1 = [
            (0, 1), (0, 4), (1, 7), (1, 14), (1, 6),
            (5, 6), (2, 3), (2, 8), (7, 8), (8, 9),
            (8, 16), (3, 9), (3, 10), (10, 11), (11, 18),
            (4, 12), (6, 13), (12, 13), (12, 19), (14, 19),
            (19, 20), (15, 20), (6, 14), (14, 15), (15, 16),
            (16, 21), (9, 24), (21, 22), (16, 22), (17, 24),
            (9, 17), (9, 10), (10, 17), (17, 18), (18, 23),
            (22, 23), (17, 23)
        ]

        edges2 = [
            (0, 1), (1, 7), (1, 14), (1, 6),
            (5, 6), (2, 3), (2, 8), (7, 8), (8, 9),
            (8, 16), (3, 9), (3, 10), (10, 11), (11, 18),
            (4, 12), (12, 13), (12, 19), (14, 19),
            (19, 20), (15, 20), (6, 14), (14, 15), (15, 16),
            (16, 21), (9, 24), (16, 22), (17, 24),
            (9, 10), (17, 18), (18, 23),
            (22, 23), (17, 23)
        ]

        edges3 = [
            (0, 1), (0, 4), (1, 7), (1, 14), (1, 6),
            (5, 6), (2, 8), (7, 8), (8, 9),
            (8, 16), (3, 9), (3, 10), (11, 18),
            (4, 12), (12, 13), (12, 19), (14, 19),
            (19, 20), (15, 20), (6, 14), (15, 16),
            (16, 21), (9, 24), (21, 22), (16, 22), (17, 24),
            (9, 17), (9, 10), (10, 17), (17, 18), (18, 23),
            (22, 23), (17, 23)
        ]

        edges4 = [
            (0, 1), (0, 4), (1, 7), (1, 14), (1, 6),
            (5, 6), (2, 3), (2, 8), (7, 8), (8, 9),
            (8, 16), (3, 9), (3, 10), (10, 11), (11, 18),
            (4, 12), (6, 13), (12, 13), (12, 19), (14, 19),
            (19, 20), (6, 14), (14, 15), (15, 16),
            (16, 21), (21, 22), (16, 22), (17, 24),
            (9, 17), (9, 10), (17, 18), (18, 23),
            (22, 23), (17, 23)
        ]

        edges5 = [
            (0, 1), (0, 4), (1, 7), (1, 14), (1, 6),
            (5, 6), (2, 3), (2, 8), (7, 8),
            (3, 10), (10, 11), (11, 18),
            (4, 12), (6, 13), (12, 13), (12, 19), (14, 19),
            (19, 20), (15, 20), (6, 14), (14, 15), (15, 16),
            (16, 21), (21, 22), (16, 22), (17, 24),
            (9, 17), (10, 17), (17, 18), (18, 23),
            (22, 23), (17, 23)
        ]

        edges6 = [
            (0, 1), (0, 4), (1, 7), (1, 6),
            (5, 6), (2, 3), (2, 8), (7, 8), (8, 9),
            (8, 16), (3, 9), (3, 10), (10, 11), (11, 18),
            (4, 12), (6, 13), (12, 13), (12, 19), (14, 19),
            (19, 20), (15, 20), (15, 16),
            (16, 21), (21, 22), (16, 22), (17, 24),
            (9, 10), (10, 17), (17, 18), (18, 23),
            (22, 23), (17, 23), (13, 19)
        ]
        edges = []
        edges.append(edges1)
        edges.append(edges2)
        edges.append(edges3)
        edges.append(edges4)
        edges.append(edges5)
        edges.append(edges6)
        i = randint(0, 5)
        return edges[i]

    # generate a large graph
    def generate_large_graph(self):
        # generate all nodes
        nodes_positions = self.large_graph_nodes()
        for x, y in nodes_positions:
            self.add_node(x, y)
        # generate all edges
        nodes_connections = self.large_graph_edges()
        for n1, n2 in nodes_connections:
            self.add_edge(self.nodes[n1], self.nodes[n2])

    # set the start node of graph algorithm
    def set_root(self, node_id):
        self.root = self.nodes[node_id]

    # draw a large graph on the screen
    def draw_large_graph(self):
        self.generate_large_graph()
        self.draw_graph()

    # display graph on panel
    def display_graph(self, times):
        for i in range(times):
            self.screen.frame()

    # update color of a node in this graph
    def update_node_color(self, node, color):
        node_id = node.get_id()
        self.nodes[node_id].change_color(color)

    # update color of a node in this graph
    def update_edge_color(self, edge, color):
        edge.change_color(color)

    # visit the edge
    def visit_edge(self, edge):
        self.update_edge_color(edge, self.visited_edge_color)
        self.draw_graph()
        self.display_graph(self.duration)

    # leave the edge
    def leave_edge(self, edge):
        self.update_edge_color(edge, self.edge_color)
        self.draw_graph()
        self.display_graph(self.duration)

    # visit the node alone
    def visit_node(self, node):
        node.mark_visited()
        self.update_node_color(node, self.visited_node_color)
        self.draw_graph()
        self.display_graph(self.duration)

    # entry for BFS
    def bfs_start(self):
        if (self.root == None):
            self.root = self.nodes[9]

        self.bfs(self.root)

    # BFS Algorithm
    def bfs(self, root):
        queue_node = deque([root, ])
        queue_edge = deque([])

        while queue_node:
            n = len(queue_node)
            for i in range(n):
                node = queue_node.popleft()
                if (not node.visited):
                    if (queue_edge):
                        edge_from = queue_edge.popleft()
                        self.visit_edge(edge_from)

                    self.visit_node(node)
                    for neighbor, edge in node.get_edges().items():
                        queue_node.append(neighbor)
                        queue_edge.append(edge)
                else:
                    if (queue_edge):
                        edge_from = queue_edge.popleft()

    # entry for DFS
    def dfs_start(self):
        if (self.root == None):
            self.root = self.nodes[9]
        self.dfs(self.root)

    # DFS Algorithm
    def dfs(self, node):
        self.visit_node(node)

        for neighbor, edge in node.get_edges().items():
            if not neighbor.visited:
                self.visit_edge(edge)
                self.dfs(neighbor)
                self.leave_edge(edge)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

from panel import Panel
import tree_cross
import tree_point


class TreeAlgorithm(object):

    def __init__(self, node_shape, duration):
        self.screen = Panel()
        if (node_shape == "cross"):
            self.tree = tree_cross.Tree(self.screen)
        else:
            self.tree = tree_point.Tree(self.screen)
        self.tree.set_duration(duration)

    # display the initial tree on the panel
    def display_init(self):
        self.tree.draw_large_tree()
        self.tree.display_tree(2)

    def inorder(self):
        self.display_init()
        self.tree.inorder_traversal()
        self.tree.display_tree(2)
        self.screen.clean_gpio()

    def preorder(self):
        self.display_init()
        self.tree.preorder_traversal()
        self.tree.display_tree(2)
        self.screen.clean_gpio()

    def postorder(self):
        self.display_init()
        self.tree.postorder_traversal()
        self.tree.display_tree(2)
        self.screen.clean_gpio()

    def levelorder(self):
        self.display_init()
        self.tree.levelorder_traversal()
        self.tree.display_tree(2)
        self.screen.clean_gpio()

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

from panel import Panel
import graph_cross
import graph_point


class GraphAlgorithm(object):

    def __init__(self, node_shape, duration, root_id):
        self.screen = Panel()
        if (node_shape == "cross"):
            self.graph = graph_cross.Graph(self.screen)
        else:
            self.graph = graph_point.Graph(self.screen)
        self.graph.set_duration(duration)
        self.root_id = root_id

    # display the initial graph on the panel
    def display_init(self):
        self.graph.draw_large_graph()
        self.graph.set_root(self.root_id)
        self.graph.display_graph(2)

    def bfs(self):
        self.display_init()
        self.graph.bfs_start()
        self.graph.display_graph(2)
        self.screen.clean_gpio()

    def dfs(self):
        self.display_init()
        self.graph.dfs_start()
        self.graph.display_graph(2)
        self.screen.clean_gpio()

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289

# Zhongkai Liu (zl777) Yefei Si(ys948)
# User interface
from pygame.locals import *  # for event MOUSE variables
import pygame
import os
import time
from tree_algorithm import TreeAlgorithm
from graph_algorithm import GraphAlgorithm
from random import randint


# initialize the pygame and set up screen
pygame.init()
WHITE = 255, 255, 255
BLACK = 0, 0, 0
GREEN = 0, 255, 0
BLUE = 0, 0, 255
RED = 255, 0, 0
size = width, height = 1000, 720
screen = pygame.display.set_mode(size)
button_ft = "HotSauce.ttf"
background = pygame.image.load('background.jpg')
level = [1, 0, 0, 0]


class Button:
    def __init__(self, text, font, posx, posy):
        self.text = text
        self.font = font
        self.posx = posx
        self.posy = posy

    def draw(self):
        button_font = pygame.font.Font(self.font, 50)
        TextSurf = button_font.render(self.text, True, WHITE)
        TextRect = TextSurf.get_rect(center=(self.posx, self.posy))
        screen.blit(TextSurf, TextRect)

    def touch(self, x, y):
        if x <= self.posx+90 and x >= self.posx-90 and y >= self.posy-50 and y <= self.posy+50:
            return 1
        else:
            return 0

    def highligth(self):
        button_font = pygame.font.Font(self.font, 70)
        TextSurf = button_font.render(self.text, True, WHITE)
        TextRect = TextSurf.get_rect(center=(self.posx, self.posy))
        screen.blit(TextSurf, TextRect)


timelimit = 600
start_time = time.time()


# generate tile
title_ft = "HotSauce.ttf"
my_font = pygame.font.Font(title_ft, 100)
title = ["Algorithm Visualizer", "Let's play", "Tree",
         "Graph", "Tree Control", "Graph Control", "Running"]
title_surface = []
title_rect = []
for i in range(len(title)):
    title_surface.append(my_font.render(title[i], True, WHITE))
    title_rect.append(title_surface[i].get_rect(center=(width/2, 200)))

# generate level 1 buttons
start_button = Button("start", button_ft, 300, 400)
quit_button = Button("quit", button_ft, 700, 400)

# generate level 2 buttons
tree_button = Button("Tree", button_ft, 300, 400)
graph_button = Button("Graph", button_ft, 700, 400)
back_button = Button("Back", button_ft, 500, 600)

# generate level 3 buttons
preorder_button = Button("Preorder", button_ft, 500, 300)
inorder_button = Button("Inorder", button_ft, 500, 375)
postorder_button = Button("Postorder", button_ft, 500, 450)
levelorder_button = Button("Levelorder", button_ft, 500, 525)
BFS_button = Button("BFS", button_ft, 300, 400)
DFS_button = Button("DFS", button_ft, 700, 400)

# generate level 4 buttons
run_button = Button("Run", button_ft, 300, 600)
back4_button = Button("Back", button_ft, 700, 600)
slow_button = Button("slow", button_ft, 300, 350)
mid = Button("mid", button_ft, 500, 350)
fast_button = Button("fast", button_ft, 700, 350)
cross_button = Button("Cross node", button_ft, 350, 450)
single_button = Button("Point node", button_ft, 650, 450)


# Start Running

code_run = True
tree = False
graph = False
level4 = ""
shape = [0, 0]
duration = [0, 0, 0]
running = 0
while code_run:
    time.sleep(0.002)
    # initialize the text surface and rect
    for event in pygame.event.get():
        if(event.type is MOUSEBUTTONDOWN):
            # initialize the text surface and rect
            pos = pygame.mouse.get_pos()
            x, y = pos
            # if it's in level 1,
            if level == [1, 0, 0, 0]:
                # and if the click position is in the quit button area, then quits the program
                if quit_button.touch(x, y):
                    level = [1, 0, 0, 0]
                    code_run = False
                # and if the click position is in the start button area
                elif start_button.touch(x, y):
                    level = [0, 1, 0, 0]

            # if it's in level 2
            elif level == [0, 1, 0, 0]:
                # if click "Tree" button
                if tree_button.touch(x, y):
                    tree = 1
                    graph = 0
                    level = [0, 0, 1, 0]
                # if click "graph" button
                elif graph_button.touch(x, y):
                    tree = 0
                    graph = 1
                    level = [0, 0, 1, 0]
                # if click "back" button
                elif back_button.touch(x, y):
                    tree = 0
                    graph = 0
                    level = [1, 0, 0, 0]
            # if it's in level 3
            elif level == [0, 0, 1, 0]:
                if tree == 1:
                    if preorder_button.touch(x, y):
                        level4 = preorder_button.text
                        level = [0, 0, 0, 1]
                    elif inorder_button.touch(x, y):
                        level4 = inorder_button.text
                        level = [0, 0, 0, 1]
                    elif postorder_button.touch(x, y):
                        level4 = postorder_button.text
                        level = [0, 0, 0, 1]
                    elif levelorder_button.touch(x, y):
                        level4 = levelorder_button.text
                        level = [0, 0, 0, 1]
                    elif back_button.touch(x, y):
                        tree = 0
                        graph = 0
                        level = [0, 1, 0, 0]
                elif graph == 1:
                    if BFS_button.touch(x, y):
                        level4 = BFS_button.text
                        level = [0, 0, 0, 1]
                    elif DFS_button.touch(x, y):
                        level4 = DFS_button.text
                        level = [0, 0, 0, 1]
                    elif back_button.touch(x, y):
                        tree = 0
                        graph = 0
                        level = [0, 1, 0, 0]
            # if it's in level 4
            elif level == [0, 0, 0, 1]:
                if slow_button.touch(x, y):
                    duration = [1, 0, 0]
                elif mid.touch(x, y):
                    duration = [0, 1, 0]
                elif fast_button.touch(x, y):
                    duration = [0, 0, 1]
                if cross_button.touch(x, y):
                    shape = [1, 0]
                elif single_button.touch(x, y):
                    shape = [0, 1]
                if run_button.touch(x, y) and shape != [0, 0] and duration != [0, 0, 0]:
                    running_surf = my_font.render(
                        level4+" Running...", True, WHITE)
                    running_rect = running_surf.get_rect(
                        center=(width/2, height/2))
                    screen.blit(background, (0, 0))
                    screen.blit(running_surf, running_rect)
                    pygame.display.flip()
                    node = ""
                    gap = 0
                    start_pt = randint(0, 24)
                    if shape == [1, 0]:
                        node = "cross"
                    elif shape == [0, 1]:
                        node = "point"
                    if duration == [1, 0, 0]:
                        gap = 10
                    elif duration == [0, 1, 0]:
                        gap = 7
                    elif duration == [0, 0, 1]:
                        gap = 5
                    if graph == 1:
                        run1 = GraphAlgorithm(node, gap, start_pt)
                        if level4 == "BFS":
                            run1.bfs()
                        elif level4 == "DFS":
                            run1.dfs()
                    elif tree == 1:
                        run1 = TreeAlgorithm(node, gap)
                        if level4 == "Preorder":
                            run1.preorder()
                        if level4 == "Inorder":
                            run1.inorder()
                        if level4 == "Postorder":
                            run1.postorder()
                        if level4 == "Levelorder":
                            run1.levelorder()

                if back4_button.touch(x, y):
                    shape = [0, 0]
                    duration = [0, 0, 0]
                    level = [0, 0, 1, 0]

    # clean the screen
    screen.blit(background, (0, 0))

    # if it's in level 1, then display level 1 buttons
    if level == [1, 0, 0, 0]:
        screen.blit(title_surface[0], title_rect[0])
        start_button.draw()
        quit_button.draw()
    # in level 2, then display level 1 buttons
    elif level == [0, 1, 0, 0]:
        screen.blit(title_surface[1], title_rect[1])
        tree_button.draw()
        graph_button.draw()
        back_button.draw()
    # in level 3, then display level 1 buttons
    elif level == [0, 0, 1, 0]:
        if tree == 1:
            screen.blit(title_surface[2], title_rect[2])
            preorder_button.draw()
            inorder_button.draw()
            postorder_button.draw()
            levelorder_button.draw()
            back_button.draw()
        elif graph == 1:
            screen.blit(title_surface[3], title_rect[3])
            back_button.draw()
            BFS_button.draw()
            DFS_button.draw()
    # in level4, display the level4 title and show duration button and shape button
    elif level == [0, 0, 0, 1]:
        if tree == 1:
            screen.blit(title_surface[4], title_rect[4])
        elif graph == 1:
            screen.blit(title_surface[5], title_rect[5])
        if shape == [1, 0]:
            cross_button.highligth()
            single_button.draw()
        elif shape == [0, 1]:
            cross_button.draw()
            single_button.highligth()
        else:
            cross_button.draw()
            single_button.draw()
        if duration == [1, 0, 0]:
            slow_button.highligth()
            mid.draw()
            fast_button.draw()
        elif duration == [0, 1, 0]:
            slow_button.draw()
            mid.highligth()
            fast_button.draw()
        elif duration == [0, 0, 1]:
            slow_button.draw()
            mid.draw()
            fast_button.highligth()
        else:
            slow_button.draw()
            mid.draw()
            fast_button.draw()
        run_button.draw()
        back4_button.draw()

    pygame.display.flip()

    now = time.time()
    if (now - start_time > timelimit):
        code_run = False